Delete node in a linked list

Time: O(1); Space: O(1); easy

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list – head = [4,5,1,9], which looks like following:

Example 1:

Input: head = {ListNode} 4->5->1->9->None, node = 5

Output: {ListNode} 4->1->9->None

Explanation:

  • You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = {ListNode} 4->5->1->9->None, node = 1

Output: {ListNode} 4->5->9->None

Explanation:

  • You are given the third node with value 1, the linked list should become 4->5->9 after calling your function.

Note:

  • The linked list will have at least two elements.

  • All of the nodes’ values will be unique.

  • The given node will not be the tail and it will always be a valid node of the linked list.

  • Do not return anything from your function.

1. Swap with Next Node

The usual way of deleting a node node from a linked list is to modify the next pointer of the node before it, to point to the node after it.

Since we do not have access to the node before the one we want to delete, we cannot modify the next pointer of that node in any way. Instead, we have to replace the value of the node we want to delete with the value in the node after it, and then delete the node after it.

Because we know that the node we want to delete is not the tail of the list, we can guarantee that this approach is possible.

[1]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))

[7]:

class Solution1(object):
    """
    Time: O(1)
    Space: O(1)
    """
    def deleteNode(self, head, node):
        """
        :type node: ListNode
        :rtype: None, do not return anything, modify node in-place instead
        """
        while head and head.next:
            if head.val == node:
                head.val, head.next = head.next.val, head.next.next
                break
            else:
                head = head.next
        return

#         if node and node.next:
#             node_to_delete = node.next
#             node.val = node_to_delete.val
#             node.next = node_to_delete.next
#             del node_to_delete

[9]:

s = Solution1()

head = ListNode(4)
head.next = ListNode(5)
head.next.next = ListNode(1)
head.next.next.next = ListNode(9)
node = 5
s.deleteNode(head, node)

exp = [4,1,9]
for val in exp:
    assert head.val == val
    head = head.next

head = ListNode(4)
head.next = ListNode(5)
head.next.next = ListNode(1)
head.next.next.next = ListNode(9)
node = 1
s.deleteNode(head, node)

exp = [4,5,9]
for val in exp:
    assert head.val == val
    head = head.next